#include <iostream>
#include <string>
#include <tuple>
#include <unordered_map>
#include <vector>

using std::string;

class Solution {
  public:
    bool isMatch(string s, string p) {
        std::vector<std::vector<bool>> dp_map;
        return isMatch_dp(s, p, 0, 0, dp_map);
        // return isMatch(s, p, 0, 0);
    }

    bool isMatch_dp(string s, string p, int si, int pi, std::vector<std::vector<bool>> dp_map) {
        // dp[si][pi] =  if s[si] == p[pi] in [a-z.] -> dp[si-1][pi-1]
        // dp[si][pi] = if p[pi] = '*' -> dp[si-1][pi] or dp[si-1][pi-1]
    }

    bool isMatch_(string s, string p, int si = 0, int pi = 0) {
        // printf("%c, %c\n", s[si], p[pi]);
        if (pi == p.size()) return si == s.size();
        if (s[si] == p[pi] or p[pi] == '.') {
            return isMatch_(s, p, si + 1, pi + 1);
        } else if (p[pi] == '*') {
            return ((s[si] == p[pi - 1] or p[pi - 1] == '.') and isMatch_(s, p, si + 1, pi)) or
                   isMatch_(s, p, si, pi + 1);
        } else if (pi < p.size() - 1 and p[pi + 1] == '*') {
            return isMatch_(s, p, si, pi + 2);
        }
        return false;
    }

    bool isMatch(string s, string p, int si, int pi) {
        // printf("%c, %c\n", s[si], p[pi]);
        if (pi == p.size()) return si == s.size();
        bool first_match = (si != s.size()) and (s[si] == p[pi] or p[pi] == '.');
        if (pi + 1 < p.size() and p[pi + 1] == '*') {
            return isMatch(s, p, si, pi + 2) or (first_match and isMatch(s, p, si + 1, pi));
        } else {
            return first_match and isMatch(s, p, si + 1, pi + 1);
        }
    }
};

void print(bool flag) {
    if (flag) {
        std::cout << "true\n";
    } else {
        std::cout << "false\n";
    }
}

int main() {
    Solution solu;
    std::vector<std::tuple<std::string, std::string>> s;
    // s.push_back(std::make_tuple("aa", "a*"));
    // s.push_back(std::make_tuple("ab", ".*c"));
    // s.push_back(std::make_tuple("mississippi", "mis*is*p*."));
    // s.push_back(std::make_tuple("aab", "c*a*b*"));
    s.push_back(std::make_tuple("aaaaaaaaaaaaab", "a*a*a*a*a*a*a*a*a*a*c"));
    for (auto tmp : s) {
        print(solu.isMatch(std::get<0>(tmp), std::get<1>(tmp)));
    }
    return 0;
}
